import java.util.HashMap;
import java.util.Map;

public class 目标和 {
    public static int sum;
    public int findTargetSumWays1(int[] nums, int target) {
        sum = 0;
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
        }

        int[][] dp = new int[nums.length][sum * 2 + 1];
        for (int i = 0; i < nums.length; i++) {
            for (int j = 0; j < sum * 2 + 1; j++) {
                dp[i][j] = -1;
            }
        }
        return dfs1(nums,target,0,0,dp);

    }

    private int dfs1(int[] nums, int target, int pos, int t, int[][] dp) {
        if (pos == nums.length) {
            return sum == target ? 1 : 0;
        }
        if (dp[pos][sum + t] != -1) {
            return dp[pos][sum + t];
        }
        // 减
        int ans = 0;
        ans = dfs1(nums,target,pos + 1,t - nums[pos],dp);
        // 加
        ans += dfs1(nums,target,pos + 1,t + nums[pos],dp);
        dp[pos][sum + t] = ans;
        return ans;
    }

    private int dfs(int[] nums, int target, int pos, int sum) {
        if (pos == nums.length) {
            return sum == target ? 1 : 0;
        }
        // 减
        int ans = 0;
        ans = dfs(nums,target,pos + 1,sum - nums[pos]);
        // 加
        ans += dfs(nums,target,pos + 1,sum + nums[pos]);
        return ans;
    }


    public int findTargetSumWays2(int[] nums, int target) {
        Map<Integer, Map<Integer,Integer>> dp = new HashMap<>();
        return dfs2(nums,target,0,0,dp);

    }

    private int dfs2(int[] nums, int target, int pos, int sum, Map<Integer, Map<Integer, Integer>> dp) {
        if (pos == nums.length) {
            return sum == target ? 1 : 0;
        }
        if (dp.containsKey(pos) && dp.get(pos).containsKey(sum)) {
            return dp.get(pos).get(sum);
        }
        // 减
        int ans = 0;
        ans = dfs2(nums,target,pos + 1,sum - nums[pos],dp);
        // 加
        ans += dfs2(nums,target,pos + 1,sum + nums[pos],dp);
        if (!dp.containsKey(pos)) {
            dp.put(pos,new HashMap<>());
        }
        dp.get(pos).put(sum,ans);
        return ans;
    }

    public int findTargetSumWays(int[] nums, int target) {
        int sum = 0;
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
        }
        if ((sum + target) % 2 != 0) {
            return 0;
        }
        int m = (sum + target) / 2;
        int[] dp = new int[m + 1];
        dp[0] = 1;
        for (int num : nums) {
            for (int j = m; j >= 0; j--) {
                dp[j] = Math.max(dp[j],dp[j - num] + 1);
            }
        }
        return dp[m];
    }
}
